<html>
    <head>
    <link rel="stylesheet" href="lmm.css" type="text/css" />
    </head>
<body class="lmm">
<!-- -*- Mode: Bolio -*- -->

<div class='chapter'>4. </div>
Sometimes it is useful to study the machine language code produced by
the Lisp Machine's compiler, usually in order to analyze an error, or
sometimes to check for a suspected compiler problem.  This chapter
explains how the Lisp Machine's instruction set works, and how to
understand what code written in that instruction set is doing.
Fortunately, the translation between Lisp and this instruction set is
very simple; after you get the hang of it, you can move back and forth
between the two representations without much trouble.  The following
text does not assume any special knowledge about the Lisp Machine,
although it sometimes assumes some general computer science background
knowledge.

<div class='section'>4.1 </div>
Nobody looks at machine language code by trying to interpret octal
numbers by hand.  Instead, there is a program called the Disassembler
which converts the numeric representation of the instruction set into a
more readable textual representation.  It is called the Disassembler
because it does the opposite of what an Assembler would do; however,
there isn't actually any assembler that accepts this input format, since
there is never any need to manually write assembly language for the Lisp
Machine.

The simplest way to invoke the Disassembler is with the Lisp function
<font class="lisp">disassemble</font>.  Here is a simple example.  Suppose we type:

<pre class="lisp">
(defun foo (x)
  (assq 'key (get x 'propname)))

(compile 'foo)

(disassemble 'foo)
</pre>

This defines the function <font class="lisp">foo</font>, compiles it, and invokes the Disassembler
to print out the textual representation of the result of the compilation.
Here is what it looks like:

<pre class="lisp">
22 MOVE D-PDL FEF|6           ;'KEY
23 MOVE D-PDL ARG|0           ;X
24 MOVE D-PDL FEF|7           ;'PROPNAME
25 (MISC) GET D-PDL
26 (MISC) ASSQ D-RETURN
</pre>

The Disassembler is also used by the Error Handler and the Inspector.
When you see stuff like the above while using one of these programs, it
is disassembled code, in the same format as the <font class="lisp">disassemble</font> function
uses.  Inspecting a compiled code object shows the disassembled code.

Now, what does this mean?  Before we get started, there is just a little
bit of jargon to learn.

The acronym PDL stands for Push Down List, and means the same thing as
Stack: a last-in first-out memory.  The terms PDL and stack will be used
interchangeably.  The Lisp Machine's architecture is rather typical of
"stack machines"; there is a stack that most instructions deal with, and
it is used to hold values being computed, arguments, and local
variables, as well as flow-of-control information.  An important use of
the stack is to pass arguments to instructions, though not all
instructions take their arguments from the stack.

The acronym "FEF" stands for Function Entry Frame.  A FEF is a compiled
code object produced by the compiler.  After the <font class="lisp">defun</font> form above
was evaluated, the function cell of the symbol <font class="lisp">foo</font> contained a
lambda expression.  Then, we compiled the function <font class="lisp">foo</font>, and the
contents of the function cell were replaced by a "FEF" object.  The
printed representation of the "FEF" object for <font class="lisp">foo</font> looks like this:

<pre class="lisp">
#&lt;DTP-FEF-POINTER 11464337 FOO&gt;
</pre>

The FEF has three parts (this is a simplified explanation): a header
with various fixed-format fields, a part holding constants and invisible
pointers, and the main body holding the machine language instructions.
The first part of the FEF, the header, is not very interesting and is
not documented here (you can look at it with <font class="lisp">describe</font> but it won't be easy
to understand what it all means).  The second part of the FEF holds various
constants referred to by the function; for example, our function <font class="lisp">foo</font>
references two constants (the symbols <font class="lisp">key</font> and <font class="lisp">propname</font>), and so
(pointers to) those symbols are stored in the FEF.  This part of the FEF
also holds invisible pointers to the value cells of all symbols that the
function uses as variables, and invisible pointers to the function cells
of all symbols that the function calls as functions.  The third part of
the FEF holds the machine language code itself.

Now we can read the disassembled code.  The first instruction looked
like this:

<pre class="lisp">
22 MOVE D-PDL FEF|6           ;'KEY
</pre>

This instruction has several parts.  The <font class="lisp">22</font> is the address of this
instruction.  The Disassembler prints out the address of each
instruction before it prints out the instruction, so that you can
interpret branching instructions when you see them (we haven't seen one
of these yet, but we will later).  The <font class="lisp">MOVE</font> is an opcode: this is a
<font class="lisp">MOVE</font> instruction, which moves a datum from one place to another.  The
<font class="lisp">D-PDL</font> is a destination specification.  The <font class="lisp">D</font> stands for
"Destination", and so <font class="lisp">D-PDL</font> means "Destination-PDL": the destination
of the datum being moved is the PDL.  This means that the
result will be pushed onto the PDL, rather than just moved to the top;
this instruction is pushing a datum onto the stack.  The next field of
the instruction is <font class="lisp">FEF|6</font>.  This is an <font class="italic">address</font>, and it specifies
where the datum is coming from.  The vertical bar serves to separate the
two parts of the address.  The part before the vertical bar can be
thought of as a <font class="italic">base register</font>, and the part after the bar can be
thought of as being an offset from that register.  <font class="lisp">FEF</font> as a base
register means the address of the FEF that we are disassembling, and so
this address means the location six words into the FEF.  So what this
instruction does is to take the datum located six words into the FEF,
and push it onto the PDL.  The instruction is followed by a "comment"
field, which looks like <font class="lisp">;'KEY</font>.  This is not a comment that any person
wrote; the disassembler produces these to explain what is going on.  The
semicolon just serves to start the comment, the way semicolons in Lisp
code do.  In this case, the body of the comment, <font class="lisp">'KEY</font>, is telling us
that the address field (<font class="lisp">FEF|6</font>) is addressing a constant (that is what
the single-quote in <font class="lisp">'KEY</font> means), and that the printed representation
of that constant is <font class="lisp">KEY</font>.  With the help of this "comment" we finally
get the real story about what this instruction is doing: it is pushing
(a pointer to) the symbol <font class="lisp">key</font> onto the stack.

The next instruction looks like this:

<pre class="lisp">
23 MOVE D-PDL ARG|0           ;X
</pre>

This is a lot like the previous instruction; the only difference is that
a different "base register" is being used in the address.  The <font class="lisp">ARG</font>
"base register" is used for addressing your arguments: <font class="lisp">ARG|0</font> means
that the datum being addressed is the zeroth argument.  Again, the
"comment" field explains what that means: the value of X (which was the
zeroth argument) is being pushed onto the stack.

The third instruction is just like the first one; it pushes the symbol
<font class="lisp">propname</font> onto the stack.

The fourth instruction is something new:

<pre class="lisp">
25 (MISC) GET D-PDL
</pre>

The first thing we see here is <font class="lisp">(MISC)</font>.  This means that this is one of
the so-called <font class="italic">miscellaneous</font> instructions.  There are quite a few of
these instructions.  With some exceptions, each miscellaneous
instruction corresponds to a Lisp function and has the same name as that
Lisp function.  If a Lisp function has a corresponding miscellaneous
instruction, then that function is hand-coded in Lisp Machine microcode.

Miscellaneous instructions only have a destination field; they don't
have any address field.  The inputs to the instruction come from the
stack: the top <font class="italic">n</font> elements on the stack are used as inputs to the
instruction and popped off the stack, where <font class="italic">n</font> is the number of arguments
taken by the function.  The result of the function is stored wherever
the destination field says.  In our case, the function being executed is
<font class="lisp">get</font>, a Lisp function of two arguments.  The top two values will be
popped off the stack and used as the arguments to <font class="lisp">get</font> (the value
pushed first is the first argument, the value pushed second is the
second argument, and so on).  The result of the call to <font class="lisp">get</font> will be
sent to the destination <font class="lisp">D-PDL</font>; that is, it will be pushed onto the stack.
(In case you were wondering about how we handle optional arguments and
multiple-value returns, the answer is very simple: functions that use
either of those features cannot be miscellaneous instructions!)  (If you
are curious as to what functions are hand-microcoded and thus available
as miscellaneous instructions, you can look at the <font class="lisp">defmic</font> forms in the
file "ai: lispm; defmic &gt;".)

The fifth and last instruction is similar to the fourth:

<pre class="lisp">
26 (MISC) ASSQ D-RETURN
</pre>

What is new here is the new value of the destination field.  This one is
called <font class="lisp">D-RETURN</font>, and it can be used anywhere destination
fields in general can be used (like in <font class="lisp">MOVE</font> instructions).  Sending
something to "Destination-Return" means that this value should be the
returned value of the function, and that we should return from this
function.  This is a bit unusual in instruction sets; rather than having
a "return" instruction, we have a destination which, when stored into,
returns from the function.  What this instruction does, then, is to
invoke the Lisp function <font class="lisp">assq</font> on the top two elements of the stack,
and return the result of <font class="lisp">assq</font> as the result of this function.

Now, let's look at the program as a whole and see what it did:

<pre class="lisp">
22 MOVE D-PDL FEF|6           ;'KEY
23 MOVE D-PDL ARG|0           ;X
24 MOVE D-PDL FEF|7           ;'PROPNAME
25 (MISC) GET D-PDL
26 (MISC) ASSQ D-RETURN
</pre>

First it pushes the symbol <font class="lisp">key</font>.  Then it pushes the value of <font class="lisp">x</font>.
Then it pushes the symbol <font class="lisp">propname</font>.  Then it invokes <font class="lisp">get</font>, which
pops the value of <font class="lisp">x</font> and the symbol <font class="lisp">propname</font> off the stack and
uses them as arguments, thus doing the equivalent of evaluating the form
<font class="lisp">(get x 'propname)</font>.  The result is left on the stack; the stack now
contains the result of the <font class="lisp">get</font> on top, and the symbol <font class="lisp">key</font>
underneath that.  Next, it invokes <font class="lisp">assq</font> on these two values, thus
doing the equivalent of evaluating <font class="lisp">(assq 'key (get x 'propname))</font>.
Finally, it returns the value produced by <font class="lisp">assq</font>.  Now, the original
Lisp program we compiled was:

<pre class="lisp">
(defun foo (x)
  (assq 'key (get x 'propname)))
</pre>

We can see that the code produced by the compiler is correct: it will do
the same thing as the function we defined will do.

In summary, we have seen two kinds of instructions so far: the <font class="lisp">MOVE</font>
instruction, which takes a destination and an address, and two of the
large set of miscellaneous instructions, which take only a destination,
and implicitly get their inputs from the stack.  We have seen two
destinations (<font class="lisp">D-PDL</font> and <font class="lisp">D-RETURN</font>), and two forms of address (<font class="lisp">FEF</font>
addressing and <font class="lisp">ARG</font> addressing).

<div class='section'>4.2 </div>
Here is a more complex Lisp function, demonstrating local variables,
function calling, conditional branching, and some other new
instructions.

<pre class="lisp">
(defun bar (y)
  (let ((z (car y)))
    (cond ((atom z)
	   (setq z (cdr y))
	   (foo y))
	  (t
	   nil))))
</pre>

The disassembled code looks like this:

<pre class="lisp">
20 CAR D-PDL ARG|0            ;Y
21 POP LOCAL|0                ;Z
22 MOVE D-IGNORE LOCAL|0      ;Z
23 BR-NOT-ATOM 30
24 CDR D-PDL ARG|0            ;Y
25 POP LOCAL|0                ;Z
26 CALL D-RETURN FEF|6        ;#'FOO
27 MOVE D-LAST ARG|0          ;Y
30 MOVE D-RETURN 'NIL
</pre>

The first instruction here is a <font class="lisp">CAR</font> instruction.  It has the same
format as <font class="lisp">MOVE</font>: there is a destination and an address.  The <font class="lisp">CAR</font>
instruction reads the datum addressed by the address, takes the <font class="lisp">car</font> of
it, and stores the result into the destination.   In our example, the
first instruction addresses the zeroth argument, and so it computes
<font class="lisp">(car y)</font>; then it pushes the result onto the stack.

The next instruction is something new: the <font class="lisp">POP</font> instruction.  It has an
address field, but it uses it as a destination rather than as a source.
The <font class="lisp">POP</font> instruction pops the top value off the stack, and stores that
value into the address specified by the address field.  In our example,
the value on the top of the stack is popped off and stored into address
<font class="lisp">LOCAL|0</font>.  This is a new form of address; it means the zeroth local
variable.  The ordering of the local variables is chosen by the
compiler, and so it is not fully predictable, although it tends to be
by order of appearance in the code; fortunately you never have to look
at these numbers, because the "comment" field explains what is going on.
In this case, the variable being addressed is <font class="lisp">z</font>.  So this instruction
pops the top value on the stack into the variable <font class="lisp">z</font>.  The first two
instructions work together to take the <font class="lisp">car</font> of <font class="lisp">y</font> and store it into
<font class="lisp">z</font>, which is indeed the first thing the function <font class="lisp">bar</font> ought to do.
(If you have two local variables with the same name, then the "comment"
field won't tell you which of the two you're talking about; you'll have
to figure that out yourself.)

The next instruction is a familiar <font class="lisp">MOVE</font> instruction, but it uses a
new destination: <font class="lisp">D-IGNORE</font>.  This means that the datum being
addressed isn't moved anywhere.  If so, then why bother doing this
instruction?  The reason is that there is conceptually a set of
<font class="italic">indicator</font> bits, as in the PDP-11.  Every instruction that moves or
produces a datum sets the "indicator" bits from that datum so that
following instructions can test them.  So the reason that the <font class="lisp">MOVE</font>
instruction is being done is so that someone can test the "indicators"
set up by the value that was moved, namely the value of <font class="lisp">z</font>.

All instructions except the branch instructions set the "indicator" bits
from the result produced and/or stored by that instruction.  (In fact,
the <font class="lisp">POP</font> in instruction 21 set the "indicators" properly, and so the
<font class="lisp">MOVE</font> at instruction 22 is superfluous.  However, the compiler is not
clever enough to notice that.)
<!-- We needn't explain that the "indicator" bits in CADR actually hold the -->
<!-- entire datum, not just a summary of its atom/cons and nil/non-nil status. -->

The next instruction is a conditional branch; it changes the flow of
control, based on the values in the "indicator" bits.  The instruction
is <font class="lisp">BR-NOT-ATOM 30</font>, which means "Branch, if the quantity was not an
atom, to location 30; otherwise proceed with execution".  If <font class="lisp">z</font> was an
atom, the Lisp Machine branches to location 30, and execution proceeds
there.  (As you can see by skipping ahead, location 30 just contains a
<font class="lisp">MOVE</font> instruction, which will cause the function to return <font class="lisp">nil</font>.)

If <font class="lisp">z</font> is not an atom, the program keeps going, and the <font class="lisp">CDR</font>
instruction is next.  This is just like the <font class="lisp">CAR</font> instruction except
that it takes the <font class="lisp">cdr</font>; this instruction pushes the value of <font class="lisp">(cdr y)</font>
onto the stack.  The next one pops that value off into the variable <font class="lisp">z</font>.

There are just two more instthe branch instructions,
which contain a branch address rather than a general base-and-offset
address.  Class IV instructions have a destination, but no address;
these are the miscellaneous instructions.

We have already seen just about all the Class I instructions.  There are
nine of them in all: <font class="lisp">MOVE</font>, <font class="lisp">CALL</font>, <font class="lisp">CALL0</font>, <font class="lisp">CAR</font>, <font class="lisp">CDR</font>, <font class="lisp">CAAR</font>,
<font class="lisp">CADR</font>, <font class="lisp">CDAR</font>, and <font class="lisp">CDDR</font>.  <font class="lisp">MOVE</font> just moves a datum from an address
to a destination; the <font class="lisp">CxR</font> and <font class="lisp">CxxR</font> instructions are the same but
perform the function on the value before sending it to the destination;
<font class="lisp">CALL</font> starts off a call to a function with some arguments; <font class="lisp">CALL0</font>
performs a call to a function with no arguments.

We've seen most of the possible forms of address.  So far we have seen
the <font class="lisp">FEF</font>, <font class="lisp">ARG</font>, and <font class="lisp">LOCAL</font> base registers.  There are two other
kinds of addresses.  One uses a "constant" base register, which
addresses a set of standard constants: <font class="lisp">NIL</font>, <font class="lisp">T</font>, <font class="lisp">0</font>, <font class="lisp">1</font>, and
<font class="lisp">2</font>.  The disassembler doesn't even bother to print out
<font class="lisp">CONSTANT|<font class="italic">n</font></font>, since the number <font class="italic">n</font> would not be even slightly
interesting; it just prints out <font class="lisp">'NIL</font> or <font class="lisp">'1</font> or whatever.  The
other kind of address is a special one printed as <font class="lisp">PDL-POP</font>, which
means that to read the value at this address, an object should be popped
off the top of the stack.

There is a higher number of Class II instructions.  The only one we've
seen so far is <font class="lisp">POP</font>, which pops a value off the stack and stores it
into the specified address.  There is another instruction called <font class="lisp">MOVEM</font>
(from the PDP-10 opcode name, meaning MOVE to Memory), which stores the
top element of the stack into the specified address, but doesn't pop it
off the stack.

Then there are seven Class II instructions to implement heavily-used
two-argument functions: <font class="lisp">+</font>, <font class="lisp">-</font>, <font class="lisp">*</font>, <font class="lisp">/</font>, <font class="lisp">LOGAND</font>, <font class="lisp">LOGXOR</font>, and
<font class="lisp">LOGIOR</font>.  These instructions take their first argument from the top of
the stack (popping them off) and their second argument from the
specified address, and they push their result on the stack.  Thus the
stack level does not change due to these instructions.

Here is a small function that shows some of these new things:

<pre class="lisp">
(defun foo (x y)
  (setq x (logxor y (- x 2))))
</pre>

The disassembled code looks like this:

<pre class="lisp">
16 MOVE D-PDL ARG|1           ;Y
17 MOVE D-PDL ARG|0           ;X
20 - '2
21 LOGXOR PDL-POP
22 MOVEM ARG|0                ;X
23 MOVE D-RETURN PDL-POP
</pre>

Instructions 20 and 21 use two of the new Class II instructions: the <font class="lisp">-</font>
and <font class="lisp">LOGXOR</font> instructions.  Instructions 21 and 23 use the <font class="lisp">PDL-POP</font>
address type, and instruction 20 uses the "constant" base register to
get to a fixnum <font class="lisp">2</font>.  Finally, instruction 22 uses the <font class="lisp">MOVEM</font>
instruction; the compiler wants to use the top value of the stack to
store it into the value of <font class="lisp">x</font>, but it doesn't want to pop it off the
stack because it has another use for it: to return it from the function.

Another four Class II instructions implement some commonly used
predicates: <font class="lisp">=</font>, <font class="lisp">&gt;</font>, <font class="lisp">&lt;</font>, and <font class="lisp">EQ</font>.  The two arguments come from the
top of the stack and the specified address; the stack is popped, the
predicate is applied to the two objects, and the result is left in the
"indicators" so that a branch instruction can test it and branch based
on the result of the comparison.  These instructions remove the top
item on the stack and don't put anything back, unlike the previous set
which put their results back on the stack.

Next, there are four Class II instructions to read, modify, and write a
quantity in ways that are common in Lisp code.  These instructions are
called <font class="lisp">SETE-CDR</font>, <font class="lisp">SETE-CDDR</font>, <font class="lisp">SETE-1+</font>, and <font class="lisp">SETE-1-</font>.  The <font class="lisp">SETE-</font>
means to set the addressed value to the result of applying the specified
one-argument function to the present value.  For example, <font class="lisp">SETE-CDR</font>
means to read the value addressed, apply <font class="lisp">cdr</font> to it, and store the
result back in the specified address.  This is used when compiling
<font class="lisp">(setq x (cdr x))</font>. which commonly occurs in loops; the other functions
are used frequently in loops, too.

There are two instructions used to bind special variables.  The first is
<font class="lisp">BIND-NIL</font>, which binds the cell addressed by the address field to
<font class="lisp">nil</font>; the second is <font class="lisp">BIND-POP</font>, which binds the cell to an object
popped off the stack rather than <font class="lisp">nil</font>.  The latter instruction pops a
value off the stack; the former does not use the stack at all.

There are two instructions to store common values into addressed cells.
<font class="lisp">SET-NIL</font> stores <font class="lisp">nil</font> into the cell specified by the address field;
<font class="lisp">SET-ZERO</font> stores <font class="lisp">0</font>.  Neither instruction uses the stack at all.

Finally, the <font class="lisp">PUSH-E</font> instruction creates a locative pointer to the cell
addressed by the specified address, and pushes it onto the stack.  This
is used in compiling <font class="lisp">(value-cell-location 'z)</font> where <font class="lisp">z</font> is an
argument or a local variable, rather than a symbol (special variable).

Those are all of the Class II instructions.  Here is a contrived
example that uses some of the ones we haven't seen, just to show
you what they look like:

<pre class="lisp">
(declare (special *foo* *bar*))

(defun weird (x y)
  (cond ((= x y)
	 (let ((*foo* nil) (*bar* 5))
	   (setq x (cdr x)))
	 nil)
	(t
	 (setq x nil)
	 (caar (value-cell-location 'y)))))
</pre>

The disassembled code looks like this:

<pre class="lisp">
24 MOVE D-PDL ARG|0           ;X
25 = ARG|1                    ;Y
26 BR-NIL 35
27 BIND-NIL FEF|6             ;*FOO*
30 MOVE D-PDL FEF|8           ;'5
31 BIND-POP FEF|7             ;*BAR*
32 SETE-CDR ARG|0             ;X
33 (MISC) UNBIND 2 bindings 
34 MOVE D-RETURN 'NIL
35 SET-NIL ARG|0              ;X
36 PUSH-E ARG|1               ;Y
37 CAAR D-RETURN PDL-POP
</pre>

Instruction 25 is an <font class="lisp">=</font> instruction; it numerically compares the top of the
stack, <font class="lisp">x</font>, with the addressed quantity, <font class="lisp">y</font>.  The <font class="lisp">x</font> is
popped off the stack, and the indicators are set to the result of the
equality test.  Instruction 26 checks the indicators, branching to 35 if
the result of the call to <font class="lisp">=</font> was NIL; that is, the machine will
branch to 35 if the two values were not equal.  Instruction 27 binds
<font class="lisp">*foo*</font> to <font class="lisp">nil</font>; instructions 30 and 31 bind <font class="lisp">*bar*</font> to <font class="lisp">5</font>.
Instruction 32 demonstrates the use of <font class="lisp">SETE-CDR</font> to compile <font class="lisp">(setq x
(cdr x))</font>, and instruction 35 demonstrates the use of <font class="lisp">SET-NIL</font> to
compile <font class="lisp">(setq x nil)</font>.  Instruction 36 demonstrates the use of
<font class="lisp">PUSH-E</font> to compile <font class="lisp">(value-cell-location 'y)</font>.

The next class of instructions, Class III, are the branching
instructions.  These have neither addresses nor destinations of the
usual sort; instead, they have branch-addresses: they say where to
branch, if the branch is going to happen.  There are several
instructions, differing in the conditions under which they will branch,
and whether they pop the stack.  Branch-addresses are stored internally
as self-relative addresses, to make Lisp Machine code relocatable, but
the disassembler does the addition for you and prints out FEF-relative
addresses so that you can easily see where the branch is going to.

The branch instructions we have seen so far decide whether to branch on
the basis of the "nil indicator"; that is, whether the last value dealt
with was <font class="lisp">nil</font> or non-<font class="lisp">nil</font>.  <font class="lisp">BR-NIL</font> branches if it was <font class="lisp">nil</font>, and
<font class="lisp">BR-NOT-NIL</font> branches if it was not <font class="lisp">nil</font>.  There are two more
instructions that test the result of the <font class="lisp">atom</font> predicate on the last
value dealt with.  <font class="lisp">BR-ATOM</font> branches if the value was an atom (that is,
if it was anything besides a cons). and <font class="lisp">BR-NOT-ATOM</font> branches if the
value was not an atom (that is, if it was a cons).  The <font class="lisp">BR</font> instruction
is an unconditional branch (it always branches).

None of the above branching instructions deal with the stack.  There are
two more instructions called <font class="lisp">BR-NIL-POP</font> and <font class="lisp">BR-NOT-NIL-POP</font>, which
are the same as <font class="lisp">BR-NIL</font> and <font class="lisp">BR-NOT-NIL</font> except that if the branch is
not done, the top value on the stack is popped off the stack.  These are
used for compiling <font class="lisp">and</font> and <font class="lisp">or</font> special forms.

Finally, there are the Class IV instructions, most of which are
miscellaneous hand-microcoded Lisp functions. The file "AI: LISPM;
DEFMIC &gt;" has a list of all the miscellaneous instructions.  Most
correspond to Lisp functions, including the subprimitives, although some
of these functions are very low level internals that may not be
documented anywhere (don't be disappointed if you don't understand all
of them).  Please do not look at this file in hopes of finding obscure
functions that you think you can use to speed up your programs; in fact,
the compiler automatically uses these things when it can, and directly
calling weird internal functions will only serve to make your code hard
to read, without making it any faster.  In fact, we don't guarantee that
calling undocumented functions will continue to work in the future.

The DEFMIC file can be useful for determining if a given function is in
microcode, although the only definitive way to tell is to compile some
code that uses it and look at the results, since sometimes the compiler
converts a documented function with one name into an undocumented one
with another name.


<div class='section'>4.3 </div>
When a function is first entered in Lisp Machine Lisp, interesting
things can happen because of the features that are invoked by use of the
various "<font class="lisp">&</font>" keywords.  The microcode performs various services when
a function is entered, even before the first instruction of the function
is executed.  These services are called for by various fields of the header
portion of the FEF, including a list called the
<font class="italic">Argument Descriptor List</font>, or <font class="italic">ADL</font>.  We won't go into the detailed
format of any of this, as it is complex and the details are not too
interesting.  The <font class="lisp">describe</font> function will disassemble it, but not
necessarily into a readily-comprehensible form.

The function-entry services include the initialization of unsupplied
optional arguments and of <font class="lisp">&AUX</font> variables.  The ADL
has a little instruction set of its own, and if the form that computes
the initial value is something simple, such as a constant, or just a
variable, then the ADL can handle things itself.  However, if things get
too complicated, instructions are needed, and the compiler generates
some instructions at the front of the function to initialize the
unsupplied variables.  In this case, the ADL specifies several different
starting addresses for the function, depending on which optional arguments
have been supplied and which have been omitted.  If all the optional
arguments are supplied, then the ADL starts the function off after all
the instructions that would have initialized the optional arguments;
since the arguments were supplied, their values should not be set, and
so all these instructions are skipped over.  Here's an example:

<pre class="lisp">
(declare (special *y*))

(defun foo (&optional (x (car *y*)) (z (* x 3)))
  (cons x z))
</pre>

The disassembled code looks like this:

<pre class="lisp">
32 CAR D-PDL FEF|6            ;*Y*
33 POP ARG|0                  ;X
34 MOVE D-PDL ARG|0           ;X
35 * FEF|11                   ;'3
36 POP ARG|1                  ;Z
37 MOVE D-PDL ARG|0           ;X
40 MOVE D-PDL ARG|1           ;Z
41 (MISC) CONS D-RETURN
</pre>

If no arguments are supplied, the function will be started at
instruction 32; if only one argument is supplied, it will be started at
instruction 34; if both arguments are supplied, it will be started at
instruction 37.  (If you do <font class="lisp">(describe 'foo)</font> and look at the
incomprehensible stuff that gets printed out, you can see the numbers 34
and 37 in lines that correspond to elements of the <font class="lisp">ADL</font>.)

The thing to keep in mind here is that when there is initialization of
variables, you may see it as code at the beginning of the function, or
you may not, depending upon whether it is too complex for the ADL to handle.
This is true of <font class="lisp">&aux</font> variables as well as unsupplied <font class="lisp">&optional</font>
arguments.

When there is an <font class="lisp">&rest</font> argument, it is passed to the function as the
zeroth local variable, rather than as any of the arguments.  This is not
really so confusing as it might seem, since an <font class="lisp">&rest</font> argument is not
an argument passed by the caller, rather it is a list of some of the
arguments, created by the function-entry microcode services.  In any case
the "comment" tells you what is going on.  In fact, one hardly ever
looks much at the address fields in disassembled code, since the
"comment" tells you the right thing anyway.  Here is an example of the
use of an <font class="lisp">&rest</font> argument:

<pre class="lisp">
(defun prod (&rest values)
  (apply #'* values))
</pre>

The disassembled code looks like this:

<pre class="lisp">
20 MOVE D-PDL FEF|6           ;#'*
21 MOVE D-PDL LOCAL|0         ;VALUES
22 (MISC) APPLY D-RETURN
</pre>

As can be seen, <font class="lisp">values</font> is referred to as <font class="lisp">LOCAL|0</font>.

Another thing the microcode does at function entry is to bind the
values of any arguments or <font class="lisp">&aux</font> variables that are special.
Thus, you won't see <font class="lisp">BIND</font> instructions doing this, but it
is still being done.

<div class='section'>4.4 </div>
We said earlier that most of the Class IV instructions are miscellaneous
hand-microcoded Lisp functions.  However, a few of them are not Lisp
functions at all.  There are two instructions that are printed as
<font class="lisp">UNBIND 3 bindings</font> or <font class="lisp">POP 7 values</font> (except that the number can be
anything up to 16 (these numbers are printed in decimal)).  These
instructions just do what they say, unbinding the last <font class="italic">n</font> values that
were bound, or popping the top <font class="italic">n</font> values off the stack.

There are also special instructions to implement the Lisp <font class="lisp">list</font>
function, which is special because it is a primitive which takes a
variable number of arguments.  Let's take a look at how the compiler
handles <font class="lisp">list</font>.

<pre class="lisp">
(defun test-list (x y)
  (list 2 x y x))
</pre>

The disassembled code looks like this:

<pre class="lisp">
16 (MISC) LIST 4 long D-RETURN
17 MOVE D-NEXT-LIST '2
20 MOVE D-NEXT-LIST ARG|0     ;X
21 MOVE D-NEXT-LIST ARG|1     ;Y
22 MOVE D-NEXT-LIST ARG|0     ;X
</pre>

The instruction <font class="lisp">LIST 4 long</font> prepares for the creation of a list of
four elements; it allocates the storage, but doesn't put anything into
it.  The destination is not used immediately, but is saved for later,
just as it is with <font class="lisp">CALL</font>.  Then the objects to be passed as arguments
are successively generated and sent to a special destination,
<font class="lisp">D-NEXT-LIST</font>.  This causes them to be put into the storage allocated
by the <font class="lisp">LIST</font> instruction.  Once the 4th such sending is done,
all the elements of the list are filled in, and the result (i.e. the
list itself) is sent to whatever destination was specified in the
<font class="lisp">LIST</font> instruction.

By the way, that is the last of the destination codes; now you have seen
all of them.  In summary, they are <font class="lisp">D-IGNORE</font>, <font class="lisp">D-PDL</font> (and <font class="lisp">D-NEXT</font>,
which is the same thing), <font class="lisp">D-LAST</font>, <font class="lisp">D-RETURN</font>, and <font class="lisp">D-NEXT-LIST</font>.

The array referencing functions, <font class="lisp">aref</font>, <font class="lisp">aset</font>, and <font class="lisp">aloc</font>, also take a
variable number of arguments, but they are handled differently.  For
one, two, and three dimensional arrays, these functions are turned into
internal functions with names <font class="lisp">ar-1</font>, <font class="lisp">as-1</font>, and <font class="lisp">ap-1</font> (with the number
of dimensions substituted for <font class="lisp">1</font>).  Again, there is no point in using
these functions yourself; it would only make your code harder to
understand but not any faster at all.  When there are more than three
dimensions, the old Maclisp way is used: arrays are referenced by
applying them as functions, using their dimensions as arguments, and
they are stored into using <font class="lisp">xstore</font>, which is like the Maclisp <font class="lisp">store</font>
but with its arguments in the other order.  You can try compiling
and disassembling some simple functions yourself if you want to see
this in action.

When you call a function and expect to get more than one value back,
a slightly different kind of function calling is used.  Here is an example
that uses <font class="lisp">multiple-value</font> to get two values back from a function call:

<pre class="lisp">
(defun foo (x)
  (let (y z)
    (multiple-value (y z)
      (bar 3))
    (+ x y z)))
</pre>

The disassembled code looks like this:

<pre class="lisp">
22 MOVE D-PDL FEF|6           ;#'BAR
23 MOVE D-PDL '2
24 (MISC) %CALL-MULT-VALUE D-IGNORE
25 MOVE D-LAST FEF|7          ;'3
26 POP LOCAL|1                ;Z
27 POP LOCAL|0                ;Y
30 MOVE D-PDL ARG|0           ;X
31 + LOCAL|0                  ;Y
32 + LOCAL|1                  ;Z
33 MOVE D-RETURN PDL-POP
</pre>

A <font class="lisp">%CALL-MULT-VALUE</font> instruction is used instead of a <font class="lisp">CALL</font>
instruction.  The destination field of <font class="lisp">%CALL-MULT-VALUE</font> is unused and
will always be <font class="lisp">D-IGNORE</font>.  <font class="lisp">%CALL-MULT-VALUE</font> takes two "arguments",
which it finds on the stack; it pops both of them.  The first one is the
function object to be applied; the second is the number of return values
that are expected.  The rest of the call proceeds as usual, but when the
call returns, the returned values are left on the stack.  The number of
objects left on the stack is always the same as the second "argument" to
<font class="lisp">%CALL-MULT-VALUE</font>.  In our example, the two values returned are left
on the stack, and they are immediately popped off into <font class="lisp">z</font> and <font class="lisp">y</font>.
There is also a <font class="lisp">%CALL0-MULT-VALUE</font> instruction, for the same
reason <font class="lisp">CALL0</font> exists.

The <font class="lisp">multiple-value-bind</font> form works similarly; here is an
example:

<pre class="lisp">
(defun foo (x)
  (multiple-value-bind (y *foo* z)
      (bar 3)
    (+ x y z)))
</pre>

The disassembled code looks like this:

<pre class="lisp">
24 MOVE D-PDL FEF|8           ;#'BAR
25 MOVE D-PDL FEF|7           ;'3
26 (MISC) %CALL-MULT-VALUE D-IGNORE
27 MOVE D-LAST FEF|7          ;'3
30 POP LOCAL|1                ;Z
31 BIND-POP FEF|6             ;*FOO*
32 POP LOCAL|0                ;Y
33 MOVE D-PDL ARG|0           ;X
34 + LOCAL|0                  ;Y
35 + LOCAL|1                  ;Z
36 MOVE D-RETURN PDL-POP
</pre>

The <font class="lisp">%CALL-MULT-VALUE</font> instruction is still used, leaving the results
on the stack; these results are used to bind the variables.

Calls done with <font class="lisp">multiple-value-list</font> work with the <font class="lisp">%CALL-MULT-VALUE-LIST</font>
instruction.  It takes one "argument" on the stack: the function object
to apply.  When the function returns, the list of values is left on the
top of the stack.  Here is an example:

<pre class="lisp">
(defun foo (x y)
  (multiple-value-list (foo 3 y x)))
</pre>

The disassembled code looks like this:

<pre class="lisp">
22 MOVE D-PDL FEF|6           ;#'FOO
23 (MISC) %CALL-MULT-VALUE-LIST D-IGNORE
24 MOVE D-PDL FEF|7           ;'3
25 MOVE D-PDL ARG|1           ;Y
26 MOVE D-LAST ARG|0          ;X
27 MOVE D-RETURN PDL-POP
</pre>

Returning of more than one value from a function is handled
by special miscellaneous instructions.  <font class="lisp">%RETURN-2</font> and <font class="lisp">%RETURN-3</font> are
used to return two or three values; these instructions take two
and three arguments, respectively, on the stack, and return from the
current function just as storing to <font class="lisp">D-RETURN</font> would.  If there are more
than three return values, they are all pushed, then the number
that there were is pushed, and then the <font class="lisp">%RETURN-N</font> instruction is
executed.  None of these instructions use their destination field.
Note: the <font class="lisp">return-list</font> function is just an ordinary miscellaneous
instruction; it takes the list of values to return as an argument on the
stack, and it returns those values from the current function.

The function <font class="lisp">lexpr-funcall</font> is compiled using a special instruction
called <font class="lisp">%SPREAD</font> to iterate over the elements of its last argument, which
should be a list.  <font class="lisp">%SPREAD</font> takes one argument (on the stack), which is
a list of values to be passed as arguments (pushed on the stack).  If
the destination of <font class="lisp">%SPREAD</font> is <font class="lisp">D-PDL</font> (or <font class="lisp">D-NEXT</font>), then the values
are just pushed; if it is <font class="lisp">D-LAST</font>, then after the values are pushed,
the function is invoked.  <font class="lisp">lexpr-funcall</font> will always compile using a
<font class="lisp">%SPREAD</font> whose destination is <font class="lisp">D-LAST</font>.  Here is an example:

<pre class="lisp">
(defun foo (a b &rest c)
  (lexpr-funcall #'format t a c)
  b)
</pre>

The disassembled code looks like this:

<pre class="lisp">
20 CALL D-IGNORE FEF|6        ;#'FORMAT
21 MOVE D-PDL 'T
22 MOVE D-PDL ARG|0           ;A
23 MOVE D-PDL LOCAL|0         ;C
24 (MISC) %SPREAD D-LAST
25 MOVE D-RETURN ARG|1        ;B
</pre>

Note that in instruction 23, the address <font class="lisp">LOCAL|0</font> is used to
access the <font class="lisp">&rest</font> argument.

The <font class="lisp">*catch</font> special form is also handled specially by the compiler.
Here is a simple example of <font class="lisp">*catch</font>:

<pre class="lisp">
(defun a ()
  (*catch 'foo (bar)))
</pre>

The disassembled code looks like this:

<pre class="lisp">
22 MOVE D-PDL FEF|6           ;'26
23 (MISC) %CATCH-OPEN D-PDL
24 MOVE D-PDL FEF|7           ;'FOO
25 CALL0 D-LAST FEF|8         ;#'BAR
26 MOVE D-RETURN PDL-POP
</pre>

The <font class="lisp">%CATCH-OPEN</font> instruction is like the <font class="lisp">CALL</font> instruction; it
starts a call to the <font class="lisp">*catch</font> function.  It takes one "argument" on
the stack, which is the location in the program that should be branched
to if this <font class="lisp">*catch</font> is <font class="lisp">*throw</font>n to.  In addition to saving that
program location, the instruction saves the state of the stack and
of special-variable binding so that they can be restored in the event
of a <font class="lisp">*throw</font>.  So instructions 22 and 23
start a <font class="lisp">*catch</font> block, and the rest of the function passes its two
arguments.  The <font class="lisp">*catch</font> function itself simply returns its second
argument; but if a <font class="lisp">*throw</font> happens during the evaluation of the
<font class="lisp">(bar)</font> form, then the stack will be unwound and execution will resume
at instruction 26.  The destination field of <font class="lisp">%CATCH-OPEN</font> is like
that of <font class="lisp">CALL</font>; it is saved on the stack, and controls what will
be done with the result of the call to the <font class="lisp">*catch</font>.  Note that
even though <font class="lisp">*catch</font> is really a Lisp special form, it is compiled
more or less as if it were a function of two arguments.

To allow compilation of <font class="lisp">(multiple-value (...) (*catch ...))</font>, there
is a special instruction called <font class="lisp">%CATCH-OPEN-MULT-VALUE</font>, which is a
cross between <font class="lisp">%CATCH-OPEN</font> and <font class="lisp">%CALL-MULT-VALUE</font>.
<font class="lisp">multiple-value-list</font> with <font class="lisp">*catch</font> is not supported.


<div class='section'>4.5 </div>
You may sometimes want to estimate the speed at which a function will
execute by examination of the compiled code.  This section gives some
rough guidelines to the relative cost of various instructions; the
actual speed may vary from these estimates by as much as a factor of
two.  Some of these speeds vary with time; they speed up as work is
done to improve system efficiency and slow down sometimes when
sweeping changes are made (for instance, when garbage collection was
introduced it slowed down some operations even when garbage collection
is not turned on.)  However these changes are usually much less than
a factor of two.

It is also important to realize that in many programs the
execution time is determined by paging rather than by CPU run time.  The
cost of paging is unfortunately harder to estimate than run time,
because it depends on dynamic program behavior and locality of data
structure.

On a conventional computer such as the pdp-10, rough estimates of the
run time of compiled code are fairly easy to make.  It is a reasonable
approximation to assume that all machine instructions take about the
same amount of time to execute.  When the compiler generates a call to
a runtime support routine, the user can estimate the speed of that
routine since it is implemented in the same instructions as the user's
compiled program.  Actual speeds can vary widely because of data
dependencies; for example, when using the <font class="lisp">plus</font> function the operation
will be much slower if an argument is a bignum than if the arguments are
all fixnums.  However, in Maclisp most performance-critical functions use
declarations to remove such data dependencies, because generic, data-dependent
operations are so much slower than type-specific operations.

Things are different in the Lisp machine.  The instruction set we have just seen
is a high-level instruction set.  Rather than specifying each individual
machine operation, the compiler calls for higher-level Lisp operations such
as <font class="lisp">cdr</font> or <font class="lisp">memq</font>.  This means that some instructions take many times
longer to execute than others.  Furthermore, in the Lisp machine we do not
use data-type declarations.  Instead the machine is designed so that all
instructions can be <font class="italic">generic</font>; that is, they determine the types of their
operands at run time.  This means that there are data dependencies that can
have major effects on the speed of execution of an instruction.  For instance,
the <font class="lisp">+</font> instruction is quite fast if both operands turn out to be fixnums,
but much slower if they are bignums.

The Lisp machine also has a large amount of microcode, both to implement certain
Lisp functions and to assist with common operations such as function calling.
It is not as easy for a user to read microcode and estimate its speed as with
compiled code, although it is a much more readable microcode than on most
computers.

In this section we give some estimates of the speed of various operations.
There are also facilities for measuring the actual achieved speed of a
program.  These will not be documented here as they are currently being changed.

We will express all times in terms of the time to execute the simplest
instruction, <font class="lisp">MOVE D-PDL ARG|0</font>.  This time is about two microseconds
and will be called a "unit".

<font class="lisp">MOVE</font> takes the same amount of time if the destination is
<font class="lisp">D-IGNORE</font> or <font class="lisp">D-NEXT</font>, or if the address is a <font class="lisp">LOCAL</font> or
<font class="lisp">PDL-POP</font> rather than an <font class="lisp">ARG</font>.  A <font class="lisp">MOVE</font> that references a
constant, via either the <font class="lisp">FEF</font> base register or the <font class="lisp">CONSTANT</font> base
register, takes about two units.  A <font class="lisp">MOVE</font> that references a special
variable by means of the <font class="lisp">FEF</font> base register and an invisible pointer
takes closer to three units.

Use of a complex destination (<font class="lisp">D-LAST</font>, <font class="lisp">D-RETURN</font>, or <font class="lisp">D-NEXT-LIST</font>)
takes extra time because of the extra work it has to do; calling a function,
returning from a function, or the bookkeeping associated with forming a list.
These costs will be discussed a bit later.

The other Class I instructions take longer than <font class="lisp">MOVE</font>.  Each memory
reference required by car/cdr operations costs about one unit.  Note
that <font class="lisp">cdr</font> requires one memory cycle if the list is compactly
cdr-coded and two cycles if it is not.  The <font class="lisp">CALL</font> instruction takes
three units.  The <font class="lisp">CALL0</font> instruction takes more, of course,
since it actually calls the function.

The Class II (no destination) instructions vary.  The <font class="lisp">MOVEM</font> and <font class="lisp">POP</font>
operations take about one unit.  (Of course they take more if <font class="lisp">FEF</font> or
<font class="lisp">CONSTANT</font> addressing is used.)  The arithmetic and logical operations and
the predicates take two units when applied to fixnums, except for multiplication and division
which take five.  The <font class="lisp">SETE-1+</font> and <font class="lisp">SETE-1-</font> instructions take
two units, the same time as a push followed by a pop; i.e. <font class="lisp">(setq x (1+ x))</font> takes
the same amount of time as <font class="lisp">(setq x y)</font>.  The <font class="lisp">SET-NIL</font> and <font class="lisp">SET-ZERO</font>
instructions take one unit.  The special-variable binding instructions take
several units.

A branch takes between one and two units.

The cost of calling a function with no arguments and no local variables
that doesn't do anything but return <font class="lisp">nil</font> is about 15 units (7 cdrs or
additions).  This is the cost of a <font class="lisp">MOVE</font> to <font class="lisp">D-LAST</font>, the simplest
form of function-entry services, and a <font class="lisp">MOVE</font> to <font class="lisp">D-RETURN</font>.  If the
function takes arguments the cost of calling the function includes the cost
of the instructions in the caller that compute the arguments.  If the function
has local variables initialized to <font class="lisp">nil</font> or optional arguments defaulted
to <font class="lisp">nil</font> there is a negligible additional cost.  The cost of having an <font class="lisp">&rest</font>
argument is less than one additional unit.  But if the function binds special
variables there is an additional cost of 8 units per variable (this includes both
binding the variables on entry and unbinding them on return).

If the function needs an ADL, typically because of complex
optional-argument initializations, the cost goes up substantially.  It's
hard to characterize just how much it goes up by, since this depends on
what you do.  Also calling for multiple values is more expensive than
simple calling.

We consider the cost of calling functions to be somewhat higher than it should
be, and would like to improve it.  But this might require incompatible system
architecture changes and probably will not happen, at least not soon.

Flonum and bignum arithmetic are naturally slower than fixnum arithmetic.
For instance, flonum addition takes 8 units more than fixnum addition, and
addition of 60-bit bignums takes 15 units more.  Note that these times include
some garbage-collection overhead for the intermediate results which have
to be created in memory.  Fixnums and small flonums do not take up any
memory and avoid this overhead.  Thus small-flonum addition takes only about
2 units more than fixnum addition.  This garbage-collection overhead is
of the "extra-pdl-area" sort rather than the full Baker garbage collector
sort; if you don't understand this don't worry about it for now.

Floating-point subtraction, multiplication, and division take just about
the same time as floating-point addition.  Floating-point execution times
can be as many as 3 units longer depending on the arguments.

The run time of a Class IV (or miscellaneous) instruction depends on the
instruction and its arguments.  The simplest instructions, predicates
such as <font class="lisp">atom</font> and <font class="lisp">numberp</font>, take 2 units.  This is basically the
overhead for doing a Class IV instruction.  The cost of a more complex
instruction can be estimated by looking at what it has to do.  You can
get a reasonable estimate by charging one unit per memory reference, car
operation, or cdr-coded cdr operation.  A non-cdr-coded cdr operation
takes two units.  For instance, <font class="lisp">(memq 'nil '(a b c))</font> takes 13 units, of
which 4 are pushing the arguments on the stack, 2 are Class IV
instruction overhead, 6 are accounted for by cars and cdrs, and 1 is
"left over".

The cost of array accessing depends on the type of array and the number
of dimensions.  <font class="lisp">aref</font> of a 1-dimensional non-indirect <font class="lisp">art-q</font> array
takes 6 units and <font class="lisp">aset</font> takes 5 units, not counting pushing the
arguments onto the stack.  (These are the costs of the <font class="lisp">AR-1</font> and
<font class="lisp">AS-1</font> instructions.)  A 2-dimensional array takes 6 units more.
<font class="lisp">aref</font> of a numeric array takes the same amount of time as <font class="lisp">aref</font> of
an <font class="lisp">art-q</font> array.  <font class="lisp">aset</font> takes 1 unit longer.  <font class="lisp">aref</font> of an
<font class="lisp">art-float</font> array takes 5 units longer than <font class="lisp">aref</font> of an <font class="lisp">art-q</font>
array.  <font class="lisp">aset</font> takes 3 units longer.

The functions <font class="lisp">copy-array-contents</font> and <font class="lisp">copy-array-portion</font>
optimize their array accessing to remove overhead from the inner loop.
<font class="lisp">copy-array-contents</font> of an <font class="lisp">art-q</font> array has a startup overhead of
8 units, not including pushing the arguments, then costs just over 2
units per array element.

The <font class="lisp">cons</font> function takes 7 units if garbage collection is turned off.
<font class="lisp">(list a b c d)</font> takes 24 units, which includes 4 units for getting the
local variables <font class="lisp">a</font>, <font class="lisp">b</font>, <font class="lisp">c</font>, and <font class="lisp">d</font>.
</body>
</html>

